perm_sort(L1,L2):-permutation(L1,L2),ordered(L2).
permutation(L1,[X|L2]):- select(X,L1,L3),permutation(L3,L2).
permutation([],[]).

ordered([X]).
ordered([X,Y|L]):- less-than-or-equal(X, Y), ordered([Y|L]).

select(X,[X|L],L).
select(X,[Y|L1],[Y|L2]):-select(X,L1,L2).

ins_sort([X|L1],L2):-sort(L1,L3),insert(X,L3,L2).
ins_sort([],[]).

insert(X,[],[X]).
insert(X,[Y|L1],[Y|L2]):-less-than(Y, X),insert(X,L1,L2).
insert(X,[Y|L],[X,Y|L]):-less-than-or-equals(X, Y).

quicksort([X|L1],L2):-
  partition(L1,X,Littles,Bigs),
  quicksort(Littles,Ls),
  quicksort(Bigs,Bs),
  append(Ls,[X|Bs],L2).
quicksort([],[]).

partition([X|L],Y,[X|Ls],Bs):- less-than-or-equal(X, Y), partition(L,Y,Ls,Bs).
partition([X|L],Y,Ls,[X|Bs]):- less-than(Y, X),	partition(L,Y,Ls,Bs).
partition([],Y,[],[]).
